package 下一个更大元素II503;

import java.util.ArrayDeque;
import java.util.Arrays;

/**
 * @author 谢阳
 * @version 1.8.0_131
 */
public class Solution {
    public static void main(String[] args) {
        int nums[] = {1, 1, 1, 1, 1};
        int[] ints = nextGreaterElements(nums);
        System.out.println(Arrays.toString(ints));
    }

    public static int[] nextGreaterElements(int[] nums) {
        int len = nums.length;
        int[] res = new int[len];
        int max = nums[0];
        int index = 0;
        for (int i = 1; i < len; i++) {
            if (max < nums[i]) {
                max = nums[i];
                index = i;
            }
        }
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        deque.push(max);
        res[index] = -1;
        int start = (index + len - 1) % len;
        while (true) {
            if (start % len == index) {
                break;
            }

            if (nums[start] == max) {
                res[start] = -1;
            } else {
                while (deque.peek() <= nums[start]) {
                    deque.pop();
                }
                res[start] = deque.peek();
            }
            deque.push(nums[start]);
            start = (start + len - 1) % len;
        }
        return res;
    }
}
